The present invention relates to communication systems. More particularly, and not by way of limitation, the present invention is directed to a method and apparatus for decoding of a turbo encoded data stream in a radio telecommunication system.
In a cellular radio telecommunication system such as a Wideband Code Division Multiple Access (WCDMA) system, data frames or packets may be encoded in a process known as turbo encoding. These systems use forward error correction (FEC) encoding (turbo code) as well as forward error detection encoding using, for example a cyclic redundancy check (CRC). The challenge is to successfully recover the transmitted encoded block of information.
The standard approach is to apply turbo decoding. Existing methods of turbo decoding are more fully described in the article, C. Berrou et al., “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes,” IEEE Trans. Commun., Vol. 44, pp 1261-1271, October 1996, which is incorporated herein by reference. Turbo codes are a new class of error-control coding systems that offer near optimal performance while requiring only moderate complexity. The widely used iterative decoding algorithm for turbo-codes is a special case of a general local message-passing algorithm for efficiently computing a posteriori probabilities in acyclic directed graphical (ADG) models (also known as “belief networks”). Iterative decoding is used and the iterative process is stopped when the CRC checks. If the CRC does not check after a predefined number of iterations, the frame is declared to be in error, and other mechanisms, such as Automatic Repeat Request (ARQ), are used to recover the lost information.
The disadvantage of this approach is that the decoder may be close to the right answer, but because the CRC detects an error, the frame is lost. In fact, the decoder may be close to the right answer early in the iterative process, and performing additional iterations to get the answer right unnecessarily utilizes system resources.
In systems employing a convolutional code instead of a turbo-code, generalized Viterbi decoding (also referred to as “list Viterbi decoding”) provides improved performance. With this approach, the decoder finds the most likely set of decoded bits, the second most likely set of decoded bits, and so on. If the CRC detects an error in the most likely set of bits, then the CRC check is applied to the second most likely, and so on. As a result, the decoder successfully decodes some frames that would have been declared in error based on conventional decoding. Viterbi decoding is more fully described in the following articles: T. Hashimoto, “A List-type Reduced-constraint Generalization of the Viterbi Algorithm,” IEEE Trans. Inf. Theory, Vol. IT-33, pp. 866-876, November 1987; C. Nill et al., “List and Soft Symbol Output Viterbi Algorithms: Extensions and Comparisons,” IEEE Trans. Commun., Vol. 43, pp. 277-287, February/March/April 1995; and N. Seshadri et al., “List Viterbi Decoding Algorithms With Applications,” IEEE Trans. Commun., Vol. 42, pp. 313-323, February/March/April 1994. Each of these articles is incorporated herein by reference.
It is noted that the generalized Viterbi approach trades error detection capability for better information recovery. This approach has been shown to provide significant gains in performance. Unfortunately, however, the algorithms developed for generalized Viterbi decoding cannot be used with turbo decoders, because turbo decoders do not perform Viterbi decoding.
It would be advantageous to have a method and apparatus for decoding of turbo encoded data that overcomes the disadvantages of existing methods while also providing significant gains in performance. The present invention provides such a method and apparatus.